HJ16 购物单

本节目标：理解“HJ16 购物单”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 描述 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。 每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。 王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。

请你帮助王强计算可获得的最大的满意度。 输入描述： 输入的第 1 行，为两个正整数N，m，用一个空格隔开： （其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）

从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q

（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）

输出描述： 输出一个正整数，为张强可以获得的最大的满意度。 示例1 输入： 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0 ==复制== 输出： 2200 ==复制== 示例2 输入： 50 520 3 520 3 510 3 010 2 010 1 0 ==复制== 输出： 130 ==复制== 说明： 由第1行可知总钱数N为50以及希望购买的物品个数m为5；第2和第3行的q为5，说明它们都是编号为5的物品的附件；第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；

所以物品的价格与重要度乘积的总和的最大值为101+203+20*3=130

这个问题是一个经典的背包问题变种，具有“分组背包”问题的特点。我们需要优化的是物品的“总满意度”，其中满意度是物品价格与其重要度的乘积。主件可以单独购买，也可以与一个或两个附件一起购买，但附件不能单独购买。

解题思路

1. 分组背包：把主件和它的附件看作一组，每组可以有多种购买方式（只买主件、主件+一个附件、主件+两个附件）。每种方式都有其成本和满意度收益。
2. 动态规划：建立一个动态规划数组 dp[i]，其中 dp[i] 表示不超过预算 i 时能得到的最大满意度。
3. 数据处理：首先解析输入，将主件和附件正确分类，计算每组的购买方式及其成本和满意度。
4. 状态转移：对于每组物品，更新 dp 数组，从大到小更新以防止重复使用物品。

对于每件物品，我们确实应该从最大预算开始向下到该物品价格所需的最小预算进行更新。这样做可以确保在计算更低预算的可能性时，较高预算的结果不会受到未处理的物品影响。这是一种典型的“不放回”背包问题处理方式。

接收总预算和物品数输入

total_budget, total_items = map(int, input().split())

将总预算转换为简化单位，因为所有价格都是10的整数倍

total_budget //= 10

初始化一个列表来存储每个物品的信息，包括主件和其附件

items_info = [{'price': 0, 'value': 0, 'attachments': []} for _ in range(total_items + 1)]

循环接收每个物品的信息

for i in range(1, total_items + 1): price, importance, is_attachment = map(int, input().split())

价格单位简化

price //= 10

计算物品的总价值（价格*重要性）

total_value = price * importance

如果是主件，直接在items_info中更新价格和价值

if is_attachment == 0: items_info[i]['price'] = price items_info[i]['value'] = total_value else: # 如果是附件，将其信息添加到对应主件的'attachments'中 items_info[is_attachment]['attachments'].append( {'price': price, 'value': total_value})

初始化动态规划数组，用于存储达到每个预算时的最大满意度

dp = [0] * (total_budget + 1)

遍历每个物品，考虑购买主件和附件的不同组合

for item in items_info[1:]:

逆序遍历预算，确保计算的是不包含当前物品时的状态

for current_budget in range(total_budget, item['price'] - 1, -1):

只购买主件

dp[current_budget] = max( dp[current_budget], dp[current_budget - item['price']] + item['value'])

遍历附件，考虑每种附件组合

for index, attachment in enumerate(item['attachments']):

购买主件+当前附件

if current_budget >= item['price'] + attachment['price']: dp[current_budget] = max(dp[current_budget], dp[current_budget - item['price'] - attachment['price']] + item['value'] + attachment['value'])

如果存在两个附件，考虑同时购买两个附件的情况

if len(item['attachments']) == 2 and index == 0: another_attachment = item['attachments'][1] total_combined_price = item['price'] +
attachment['price'] + another_attachment['price'] total_combined_value = item['value'] +
attachment['value'] + another_attachment['value']

购买主件+两个附件

if current_budget >= total_combined_price: dp[current_budget] = max( dp[current_budget], dp[current_budget - total_combined_price] + total_combined_value)

输出最大满意度，转换回原始的货币单位

print(dp[total_budget] * 10)

您的提问指向了动态规划中背包问题的一个核心特性：状态转移。当我们使用 dp 数组来解决背包问题时，我们确实在每次迭代中更新 dp 数组，但关键在于这种更新是建立在前一个状态的基础上的。换句话说，每次更新 dp[budget] 时，我们都是在考虑“如果现在加入这个新的物品或物品组合，可以得到更大的满意度吗？”

详细解释

1. 累积更新:

• 当我们从第一个 items_info 遍历完毕后，dp 数组已经包含了用最少的预算达到最大满意度的方法。
• 当我们开始处理第二个 items_info 时，我们不是从零开始，而是在第一个 items_info 已经填充好的 dp 数组的基础上进行更新。这意味着第二个 items_info 的处理是考虑了前面物品购买情况的继续。

2. 不是单独购买:

• 每次更新 dp 并不意味着忘记或抛弃之前的物品。实际上，这是在说：“如果我在买了前面的物品后，还有足够的预算买这个新物品，我的满意度会提高吗？”
• 因此，dp[budget] 最终存储的是可能的最大满意度，这可能包括多个主件及其附件的任何组合。

3. 逆序遍历的重要性:

• 我们之所以逆序遍历预算，是为了保证每件物品只被计算一次（避免重复使用同一物品）。
• 如果我们正序遍历，就可能出现使用同一物品多次的情况，这会违背题目中“每件物品只能购买一次”的规则。

核心观点

• dp 数组是累积的：每一步的更新都是基于之前所有步骤的结果，而不是单独考虑当前物品。
• 多物品组合：通过逐个考虑物品（及其可能的附件组合），我们实际上是在不断尝试不同的组合方式，每次迭代寻找能够在当前预算下达到的最大满意度。

结论

所以，这种方法并不是在计算只购买当前 items_info 的最大满意度，而是在不断尝试添加新的物品组合到已经考虑的物品组合中，从而在总预算限制下尽可能提高满意度。每次循环结束时，dp[budget] 里存储的是考虑到当前所有物品时，各个预算水平下的最大满意度。这样，当所有物品都被考虑过后，dp[total_budget] 就包含了使用总预算达到的最大满意度，这个值是所有合法物品组合的最优结果。